package com.cb2.algorithm.leetcode;

/**
 * <a href='https://leetcode.cn/problems/maximum-subarray/'>最大子数组和(Maximum Subarray)</a>
 * <p>给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。</p>
 * <p>子数组【子数组 是数组中连续的 非空 元素序列。】是数组中的一个连续部分。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 *  示例 1：
 *      输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
 *      输出：6
 *      解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
 *
 *  示例 2：
 *      输入：nums = [1]
 *      输出：1
 *
 *  示例 3：
 *      输入：nums = [5,4,-1,7,8]
 *      输出：23
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>1 <= nums.length <= 10^5</li>
 *     <li>-10^4 <= nums[i] <= 10^4</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2025/2/17 13:49
 */
public class LC0053MaximumSubarray_M {
    static class Solution {
        public int maxSubArray(int[] nums) {
            // 对原数组内容作了修改。
            //int res = nums[0];
            //for (int i = 1; i < nums.length; i++) {
            //    if (nums[i - 1] > 0) {
            //        nums[i] += nums[i - 1];
            //    }
            //    res = Math.max(res, nums[i]);
            //}
            //return res;
            // 如果不对原数组内容进行修改，使用一个变量保存最大和。
            int res = nums[0];
            int preVal = 0;
            for (int currVal : nums) {
                preVal = Math.max(currVal, preVal + currVal);
                res = Math.max(res, preVal);
            }
            return res;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.maxSubArray(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4}));
        System.out.println(solution.maxSubArray(new int[]{1}));
        System.out.println(solution.maxSubArray(new int[]{5, 4, -1, 7, 8}));
    }
}
